public class NumsSort {
}
class NumsSortSolution{
    void quickSort(int[] nums,int l,int r){
        if(l<r){
            int partion = partionSort(nums,l,r);
            quickSort(nums,l,partion-1);
            quickSort(nums,partion+1,r);
        }
    }
    int partionSort(int[] nums,int l,int r){
        int index = l+1;
        int num = nums[l];
        for(int i=l+1;i<=r;i++){
            if(nums[i]<num)swap(nums,index++,i);
        }
        swap(nums,index-1,l);
        return index-1;
    }
    void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    void mergeSort(int[] nums,int l,int r){
        if(l<r){
            int m = (l+r)/2;
            mergeSort(nums,l,m);
            mergeSort(nums,m+1,r);
            merge(nums,l,m,r);
        }
    }
    void merge(int[] nums,int l,int m,int r){
        int li = l;
        int mi = m+1;
        int[] res = new int[r-l+1];
        int index = 0;
        while(li<=m&&mi<=r){
            if(nums[li]<nums[mi])
                res[index++] = nums[li++];
            else
                res[index++] = nums[mi++];
        }
        while(li<=m){
            res[index++] = nums[li++];
        }
        while(mi<=r){
            res[index++] = nums[mi++];
        }
        for(int i=l;i<=r;i++)
            nums[i] = res[i-l];
    }
    void heapSort(int[] nums){
        int n = nums.length-1;
        for(int i=n/2;i>=0;i--){
            heapify(nums,i,n);
        }
        for(int i=n;i>0;i--){
            swap(nums,0,i);
            heapify(nums,0,i-1);
        }
    }
    void heapify(int[] nums,int s,int r){
        int largest = s;
        int left = 2*s+1;
        int right = 2*s+2;
        while(left<=r){
            if(nums[left]>nums[largest]){
                largest = left;
            }else if(right<=r&&nums[right]>nums[largest]){
                largest = right;
            }
            if(largest!=s){
                swap(nums,largest,s);
                s = largest;
                left = 2*s+1;
                right = 2*s+2;
            }
            else break;
        }
    }
}
